package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 剑指offer
 * 序列化二叉树
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：405269
 * 本题知识点： 队列 树
 *  算法知识视频讲解
 * 题目描述
 * 请实现两个函数，分别用来序列化和反序列化二叉树
 *
 * 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
 *
 * 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
 *
 * 例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树
 * 示例1
 * 输入
 * 复制
 * {8,6,10,5,7,9,11}
 * 返回值
 * 复制
 * {8,6,10,5,7,9,11}
 */
public class SerializeBinaryTree {

    @Test
    public void test() {

        TreeNode root = new TreeNode(8);

        TreeNode treeNode = root;

        treeNode.left = new TreeNode(4);
        treeNode.right = new TreeNode(12);
        treeNode.left.left = new TreeNode(2);
        treeNode.right.left = new TreeNode(10);
        treeNode.left.left.left = new TreeNode(1);
        String serialize = Serialize(root);
        System.out.println(serialize);
        TreeNode deserialize = Deserialize(serialize);
        System.out.println(deserialize);
        System.out.println();
    }

    String Serialize(TreeNode root) {

        if (root == null) {
            return "";
        }

        ArrayList<TreeNode> levelTreeNodes = new ArrayList<>();
        StringBuffer str = new StringBuffer();
        levelTreeNodes.add(root);
        str.append(root.val + " ");

        levelTransversal(str, levelTreeNodes);

        return str.toString();
    }

    private void levelTransversal(StringBuffer str, ArrayList<TreeNode> preLevelTreeNodes) {

        boolean flag = false;

        for (TreeNode preLevelTreeNode : preLevelTreeNodes) {
            if (preLevelTreeNode != null) {
                flag = true;
            }
        }

        if (!flag) {
            return;
        }

        ArrayList<TreeNode> levelTreeNodes = new ArrayList<>();

        for (TreeNode preLevelTreeNode : preLevelTreeNodes) {
            if (preLevelTreeNode != null) {
                if (preLevelTreeNode.left != null) {
                    levelTreeNodes.add(preLevelTreeNode.left);
                    str.append(preLevelTreeNode.left.val + " ");
                } else {
                    levelTreeNodes.add(null);
                    str.append("# ");
                }
                if (preLevelTreeNode.right != null) {
                    levelTreeNodes.add(preLevelTreeNode.right);
                    str.append(preLevelTreeNode.right.val + " ");
                } else {
                    levelTreeNodes.add(null);
                    str.append("# ");
                }
            } else {
                levelTreeNodes.add(null);
                levelTreeNodes.add(null);
                str.append("# ");
                str.append("# ");
            }
        }

        levelTransversal(str, levelTreeNodes);
    }

    TreeNode Deserialize(String str) {
        if (str == "") {
            return null;
        }

        String[] val = str.split(" ");

        TreeNode root = new TreeNode(Integer.parseInt(val[0]));

        ArrayList<TreeNode> levelTreeNodes = new ArrayList<>();
        levelTreeNodes.add(root);

        levelTransversal(1, 0, 1, val, levelTreeNodes);

        return root;
    }

    private void levelTransversal(int addCount, int begin, int length, String[] val, ArrayList<TreeNode> treeNodes) {

        if (addCount == 0) {
            return;
        }

        addCount = 0;
        for (int i = begin; i < begin + length; i++) {
            if (treeNodes.get(i) == null) {
                treeNodes.add(null);
                treeNodes.add(null);
            } else {
                if (2 * i + 1 < val.length) {
                    if (!val[2 * i + 1].equals("#")) {
                        TreeNode treeNode = new TreeNode(Integer.parseInt(val[2 * i + 1]));
                        treeNodes.get(i).left = treeNode;
                        treeNodes.add(treeNode);
                        addCount++;
                    } else {
                        treeNodes.add(null);
                    }
                }
                if (2 * i + 2 < val.length) {
                    if (!val[2 * i + 2].equals("#")) {
                        TreeNode treeNode = new TreeNode(Integer.parseInt(val[2 * i + 2]));
                        treeNodes.get(i).right = treeNode;
                        treeNodes.add(treeNode);
                        addCount++;
                    } else {
                        treeNodes.add(null);
                    }
                }
            }
        }

        levelTransversal(addCount, begin + length, length * 2, val, treeNodes);
    }
}
